package com.dayuanit.dy17.mix.search;

public class BinarySearch {


    private static void find1(String words[], String targetWord) {
        int low = 0;
        int high = words.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (words[mid].equals(targetWord)) {
                System.out.println("find targetWord");
                break;
            } else if (words[mid].compareTo(targetWord) < 0) {
                low = mid + 1;
            } else if (words[mid].compareTo(targetWord) > 0) {
                high = mid - 1;
            }
        }
    }

    //使用递归的方式  要占用更多的内存空间
    private static void find2(String words[], String targetWord, int low, int high) {
        //递归的退出条件
        if (low > high) {
            return;
        }

        int mid = low + (high - low) / 2;
        if (words[mid].equals(targetWord)) {
            System.out.println("find targetWord");
            return;
        } else if (words[mid].compareTo(targetWord) < 0) {
            find2(words, targetWord, mid + 1, high);
        } else if (words[mid].compareTo(targetWord) > 0) {
           find2(words, targetWord, low, mid - 1);
        }
    }

    public static void main(String[] args) {
        //二分查找 也叫折半查找 被查找的元素要有序
        String[] words = {"a", "b", "c", "f", "k", "y", "z"};
        String w = "c";

        //O(n)
//        for (String word : words) {
//            if (w.equals(word)) {
//                System.out.println("find " + w);
//            }
//        }

//        find1(words, w);

        //二分查找 O(logn)
        find2(words, w, 0, words.length - 1);

        //评价一个算法的好坏，就看时间复杂度和空间复杂度。有时候，会做出空间换时间的操作，也是常有的。

        //二分查找(O(logn)的时间复杂度)，散列表(O(1)的时间复杂度)
    }
}
